package A_sort;

public class D_MergeSort {

    /**
     * 归并排序 时间复杂度O(NlogN) 空间复杂度O(N)
     * 时间复杂度低的原因：选择排序，冒泡排序，插入排序每次比较都是相互独立的，浪费了大量比较
     * 归并排序每一次比较都是向下传递的，形成较小的有序的片段在进行合并，比较信息被记录了下来
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr,0,arr.length-1);
    }

    private static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        // 二分 让左侧部分有序
        process(arr, L, mid);
        // 让右侧部分有序
        process(arr, mid + 1, R);
        // 合并左右两侧
        merge(arr, L, mid, R);
    }

    private static void merge(int[] arr, int L, int M, int R) {
        // 开辟一个新的数组 长度为需要排序数组的长度
        int[] temp = new int[R - L + 1];
        // temp的指针 指向temp的下标
        int i = 0;
        // 左侧部分的指针 指向左侧部分的起始位置
        int point1 = L;
        // 右侧部分的指针 指向右侧部分的起始位置
        int point2 = M + 1;
        // 如果左侧右侧指针都没有越界
        // 左侧部分指向的值小于右侧部分
        // 将左侧指针指向的值录入新的数组 新数组指针向右偏移1 左侧指针向右偏移1
        // 反之将右侧指针指向的值录入新的数组 新数组指针右侧偏移1 右侧指针向右偏移1
        while (point1 <= M && point2 <= R) {
            temp[i++] = arr[point1] <= arr[point2] ? arr[point1++] : arr[point2++];
        }
        // 下面连个while只会命中一个
        // 如果左侧指针越界 则左侧数组全部录入进新的数组，将右侧数组剩余量录入新的数组
        while (point1 <= M) {
            temp[i++] = arr[point1++];
        }
        // 如果右侧指针越界 则右侧数组全部录入进新的数组，将左侧数组剩余量录入新的数组
        while (point2 <= R) {
            temp[i++] = arr[point2++];
        }
        // 将新数组中排好顺序的数组替换原有数组
        for (int j = 0; j < temp.length; j++) {
            arr[L + j] = temp[j];
        }
    }
}
